package com.leetcode.easy;

import java.util.ArrayList;
import java.util.List;

/**
 * @Classname Generate
 * @Description 杨辉三角
 * @Date 2020/9/21 16:00
 * @Created by zfl
 */
public class Generate {

    /**
     * @param numRows
     * @return
     * 内存占用过大
     */
    public static List<List<Integer>> generate(int numRows) {
        List<List<Integer>> listGen = new ArrayList<>(numRows);
        if(numRows == 1) {
            List<Integer> list = new ArrayList<>();
            list.add(1);
            listGen.add(list);
            return listGen;
        }

        listGen = generate(numRows - 1);
        List<Integer> gen = new ArrayList<>();
        for (int i = 0; i < numRows; i++) {
            if(i == 0 || i == numRows - 1) {
                gen.add(1);
            }else{
                gen.add(listGen.get(numRows - 2).get(i - 1) + listGen.get(numRows - 2).get(i));
            }
        }
        return listGen;
    }

    /**
     * @param numRows
     * @return
     * 执行用时：1 ms, 在所有 Java 提交中击败了77.14%的用户
     * 内存消耗：36.4 MB, 在所有 Java 提交中击败了59.80%的用户
     */
    public static List<List<Integer>> generate2(int numRows) {
        List<List<Integer>> listGen = new ArrayList<>();
        for(int i = 0; i < numRows; i++) {
            if(i == 0) {
                List<Integer> list = new ArrayList();
                list.add(1);
                listGen.add(list);
            } else if(i == 1) {
                List<Integer> list = new ArrayList<>();
                list.add(1);
                list.add(1);
                listGen.add(list);
            }else{
                List<Integer> list = new ArrayList<>();
                for (int j = 0; j <= i; j++) {
                    if(j == 0 || j == i) {
                        list.add(1);
                    }else {
                        list.add(listGen.get(i - 1).get(j - 1) + listGen.get(i - 1).get(j));
                    }
                }
                listGen.add(list);
            }
        }
        return listGen;
    }

    /**
     * @param numRows
     * @return
     * 执行用时：1 ms, 在所有 Java 提交中击败了77.14%的用户
     * 内存消耗：36.2 MB, 在所有 Java 提交中击败了95.14%的用户
     */
    public static List<List<Integer>> generate3(int numRows) {
        List<List<Integer>> triangle = new ArrayList<List<Integer>>();

        if(numRows == 0) {
            return triangle;
        }
        triangle.add(new ArrayList<>());
        triangle.get(0).add(1);

        for(int rowNum = 1; rowNum < numRows; rowNum++){
            List<Integer> row = new ArrayList<>();
            List<Integer> prevRow = triangle.get(rowNum - 1);
            row.add(1);
            for (int j = 1; j < rowNum; j++) {
                row.add(prevRow.get(j - 1) + prevRow.get(j));
            }
            row.add(1);
            triangle.add(row);
        }

        return triangle;
    }

    /**
     * @param rowIndex
     * @return
     * 杨辉三角2
     * 执行用时：1 ms, 在所有 Java 提交中击败了84.67%的用户
     * 内存消耗：36.6 MB, 在所有 Java 提交中击败了16.83%的用户
     */
    public static List<Integer> generate4(int rowIndex) {
        if(rowIndex == 0) {
            List<Integer> list = new ArrayList<>();
            list.add(1);
            return list;
        }
        List<Integer> listGen = generate4(rowIndex - 1);
        List<Integer> gen = new ArrayList<>();
        for (int i = 0; i <= rowIndex; i++) {
            if(i == 0 || i == rowIndex) {
                gen.add(1);
            }else{
                gen.add(listGen.get(i - 1) + listGen.get(i));
            }
        }
        return gen;
    }
}
